package com.samxcode.leetcode;

/**
 * Given a sorted array of integers, find the starting and ending position of a given target value.
 * 
 * Your algorithm's runtime complexity must be in the order of O(log n).
 * 
 * If the target is not found in the array, return [-1, -1].
 * 
 * solutions: binary search and extend respectively the index to the left-most and right-most
 * position which the value equals to the target.
 * 
 * @author Sam
 *
 */
public class SearchForARange {

    public static void main(String[] args) {
        int nums[] = { 0, 0, 1, 1, 3 };
        System.out.println(searchRange(nums, 1)[0]);
        System.out.println(searchRange(nums, 1)[1]);
    }


    public static int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int end = right;
        int medium;
        while (left <= right) {
            medium = (left + right) / 2;
            if (nums[medium] == target) {
                left = medium;
                while (end > medium && nums[medium + 1] == nums[medium])
                    medium++;
                while (left > 0 && nums[left - 1] == nums[left])
                    left--;
                return new int[] { left, medium };
            } else if (nums[medium] > target) {
                right = --medium;
            } else {
                left = ++medium;
            }
        }
        return new int[] { -1, -1 };
    }
}
